'''
难度 困难
标签 贪心
题目链接 https://leetcode.cn/problems/reducing-dishes/description/
'''


from typing import List


class Solution:
    # 贪心算法
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        # 从大到小排序
        satisfaction.sort(reverse=True)
        
        # 先选最大，直到后续选择一个菜的和比选择之前和更小 就停止
        # 已选所有菜品单值和 不含系数时长 只含菜品本身数值
        结果, 已选所有菜品单值和 = 0, 0
        for i in satisfaction:
            # 当 1*s3 + 2*s2 + 3*s1 > 1*s2 + 2*s1 推导出 s3 + s2 + s1 > 0 时 才能选择进来
            if 已选所有菜品单值和 + i > 0:
                已选所有菜品单值和 += i
                # 每次新加入一道菜 都相当于累加一次 已选所有菜品单值和
                结果 += 已选所有菜品单值和

        return 结果

if __name__ == '__main__':
    s = Solution()
    参数 = [
        [[-1,-8,0,5,-9]],
        [[4,3,2]],
        [[-1,-4,-5]],
    ]
    预期 = [
        14,
        20,
        0,
    ]
    for k,v in enumerate(参数):
        r = s.maxSatisfaction(v[0])
        if r != 预期[k]:
            print("第{}个case不通过 期望={} 结果={}\n".format(
                k+1,
                预期[k],
                r
            ))